<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /*
      tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
      思路：tickets是所拥有的机票数组。可以将tickets进行拆分，拆分成from和to数组，并建立映射关系，
      这样就可以知道from对应哪几个to

      ②：递归加回溯，从JFK开始，判断可以到达哪几个to，然后依次递归回溯。
      重点：backTracking()的参数 因为它并不像排列组合一样求出所有组合或排列，所以params1:city表面已经前往的城市
      use:表面目前去过的城市数

      终止条件: if(use==tickets.length)  return true  //机票全用完了，自然return true  注意：JFK是起点，机票4张
                剪枝条件  如果下一站为空或不存在map.get(city).length==0
                          (且机票还未用完的前提下)那么说明这条路没法到，return false

      集合：即当前城市可前往的下一站城市集合  map.get(city)
      重点：去过的城市需要被删除，不能再次飞  比如  北京:[广州，上海] 已经去过广州了，下一次就不能再去广州

      */
      var findItinerary = function (tickets) {
        let res = ['JFK']
        let map = new Map()
        for (let i in tickets) {
          let from = tickets[i][0]
          let to = tickets[i][1]
          if (!map.has(from)) {
            map.set(from, [])
          }
          map.get(from).push(to)
        }
        for (let [key, value] of map) {
          value.sort()
        }
        function backTracking(city, use) {
          if (use == tickets.length) {
            return true
          }
          //如果机票未用光
          let nextCities = map.get(city)
          if (!nextCities || nextCities.length == 0) {
            return false
          }
          for (let i = 0; i < nextCities.length; i++) {
            let nextCity = nextCities[i]
            nextCities.splice(i, 1)
            res.push(nextCity)
            //如果下一次遍历到的是true那么return true。
            //注意，这里不能用nextCities[i]了，因为数组被改变了
            if (backTracking(nextCity, use + 1)) {
              return true
            }
            //否则：弹出元素，并恢复
            else {
              nextCities.splice(i, 0, nextCity)
              res.pop()
            }
          }
        }
        backTracking('JFK', 0)
        return res
      }
      console.log(
        findItinerary([
          ['JFK', 'SFO'],
          ['JFK', 'ATL'],
          ['SFO', 'JFK'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL'],
          ['ATL', 'AAA'],
          ['AAA', 'BBB'],
          ['BBB', 'ATL']
        ])
      )
    </script>
  </body>
</html>
